package msb.class02;

import java.util.ArrayList;
import java.util.Stack;

import org.junit.Assert;
import org.junit.Test;
import common.util.ArrayUtil;

/**
 * 设计一个栈
 * 1. pop push getMin时间复杂度O(1)
 * 2. 可以使用现成的栈结构
 * <p>
 * 实现
 * 2个栈，数据栈、最小栈
 */
public class Code06_GetMinStack {

    private final Stack<Integer> normalStack = new Stack<>();
    private final Stack<Integer> minStack = new Stack<>();

    public void push(Integer num) {
        normalStack.push(num);
        if (minStack.isEmpty()) {
            minStack.push(num);
        } else {
            minStack.push(Math.min(minStack.peek(), num));
        }
    }

    public Integer pop() {
        minStack.pop();
        return normalStack.pop();
    }

    public Integer getMin() {
        return minStack.peek();
    }

    @Test
    public void test() {

        for (int i = 0; i <100 ; i++) {
            int[] instant = ArrayUtil.instant(100, 100);
            ArrayList<Integer> list = new ArrayList<>();
            Stack<Integer> stack = new Stack<>();
            Code06_GetMinStack code06_getMinStack = new Code06_GetMinStack();
            for (Integer e : instant) {
                code06_getMinStack.push(e);
                stack.push(e);
                list.add(e);
            }

            for (int j : instant) {
                Integer listMin = list.stream().min(Integer::compareTo).get();
                Assert.assertEquals(code06_getMinStack.getMin(), listMin);
                Assert.assertEquals(code06_getMinStack.pop(), stack.pop());
                list.remove(list.size() - 1);
            }
        }
    }

}
